\documentclass[runningheads,a4paper]{llncs}
\usepackage[margin=1.54in]{geometry}
\usepackage{amssymb,amsmath,authblk}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{color}

\usepackage{url}
%\urldef{\mailsa}\path|daniel.smith@nist.gov|
%\urldef{\mailsb}\path|ray.perlner@nist.gov|
%\urldef{\mailsc}\path|dustin.moody@nist.gov|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}


%===============Definitions==========================


\newcommand{\bdf}{\begin{definition}}
\newcommand{\edf}{\end{definition}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bsp}{\begin{split}}
\newcommand{\esp}{\end{split}}
\newtheorem{Thm}{Theorem}
\newtheorem{Lem}{Lemma}
\newtheorem{Cor}{Corollary}
\newtheorem{Prop}{Proposition}[chapter]
\newtheorem{Def}{Definition}
\newtheorem{Rem}{Remark}
\newcommand{\Z}{\mathbb{Z}}
\def\mathbi#1{\textbf{\em #1}}


%===================End Definitions======================

%===============Perspective Definitions=====================

%\def\xa{108}
%\def\ya{-106}
%\def\za{80}

\def\xdirx{-0.996}
\def\xdiry{0.087}
\def\ydirx{0.614}
\def\ydiry{0.43}
\def\zdirx{0.0}
\def\zdiry{1}

%=============End Perspective Definitions====================

%==============Color Definitions=======================

\definecolor{lightgray}{rgb}{0.85,0.85,0.85}
\definecolor{mediumgray}{rgb}{0.75,0.75,0.75}
\definecolor{darkgray}{rgb}{0.45,0.45,0.45}

%============End Color Definitions======================

%===============Notation Macros=====================

\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
  }}

\newcommand{\rkappa}{\raisebox{\depth}{\rotatebox{270}{$\mathcal{K}$}}}

%=============End Notation Macros====================


\begin{document}

\mainmatter

\title{Thermodynamic Analysis of Classical and Quantum Algorithms for Preimage and Collision Search Problems}

\titlerunning{Thermodynamic Analysis of Search Problems}

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle

\begin{abstract}
One of the earliest proposed applications of quantum computers was the quadratic speedup of classical brute force search represented by Grover's algorithm. Since then various successor algorithms have been applied to a variety of oracle problems including collision finding and claw finding. Such algorithms have typically been analyzed in terms of query complexity, which is a somewhat unphysical model of the cost of computation in the real world. Other models of these algorithms, such as the quantum circuit model and the quantum random access machine model of computation give more realistic, but sometimes conflicting answers regarding how much advantage the quantum algorithm provides over the corresponding classical algorithm.

We instead adapt Bennett's Brownian model of computation to directly estimate the cost of both classical and quantum operations in terms of time, energy, and memory. We apply this model to compare the best known quantum algorithms for collision search and preimage search to their classical counterparts. In the collision search case, our analysis agrees with previous analysis, based on the gate model of quantum computation, suggesting that quantum computation provides no improvement over the best known classical algorithm. More surprisingly, we find that a Brownian implementation of randomized classical search can achieve the same tradeoffs between time, memory and energy as Grover's algorithm (at least up to logarithmic factors.) This implementation uses thermal noise to drive a random walk within the internal state of a mostly unpowered circuit. 
 
\keywords{Reversible Computation, Quantum Computation, Collision Search, Preimage Search, Grover's algorithm}
\end{abstract}

\section{Introduction}

\section{Bennett's Brownian Computation Model}

In contrast to ballistic models of computation, which are generally assumed to be unrealistic, Brownian computers are assumed to operate near thermal equilibrium at a finite temperature, $T$. As in the case of ballistic computers, to avoid being constrained to consume at least $kT ln 2$ energy per bit operation by the Landauer limit, the program for a Brownian computer is encoded as a reversible circuit. In the absence of any driving force, the state of the computing system at any given time may be described as a random walk on that circuit, with state transitions that undo a useful computation happening as often as those that perform it. In order for computations to proceed forward at a nonzero expected rate, a driving force, dissipating an energy of $\epsilon$ per gate is imposed. This leads forward transitions within the circuit to occur $e^{\frac{\epsilon}{kT}}$ times more often than backward transitions, resulting in a net forward computation rate proportional to $\frac{\epsilon}{kT}$ for $\epsilon$ small compared to $kT$.

Some additional costs are required in order for Brownian computation to be achieved fault-tolerantly. Energy barriers must be imposed to prevent transitions to physical states outside the reversible circuit, representing the prescribed computation path. In order to suppress the probability of such undesirable transitions so that a circuit of size $G$ can be completed with high probability, the size of these energy barriers must at least be on the order of $kT ln (\frac{kT}{\epsilon}\cdot G).$ Additionally, dissipating a ``latching" energy of about $kT ln (\frac{kT}{\epsilon})$ during the computation's final step is required to suppress backwards transitions once the computation has reached its halting state.

These costs may, however, be assumed to be negligible in a number of important cases: In particular, the latching energy will be negligible when $\frac{\epsilon}{kT}$ is at least logarithmically more than $\frac{1}{G}$. Additionally, establishing energy barriers to non-computational paths is likely to be a negligible cost when a description of the circuit can be expressed in a physically compact form, for example, using looping constructs. More precisely, if we assume that the circuit can be compressed into a program of size $m_0$, then the cost of imposing energy barriers should be on the order of $m_0\cdot kT ln (\frac{kT}{\epsilon}\cdot G).$ This cost is negligible as long as $\frac{\epsilon}{kT}$ is significantly larger than $e^{-\frac{G}{m_0}}$.

In fact, the initialization cost may be less than this, since it may be more realistic to think of the initialization process as rearranging the energy barriers already present in the available raw materials for constructing our computer. The cost is then determined by the Landauer limit and the information content of the circuit, including appropriately large energy barriers. Since the size of these barriers does not need to be precislely specified, but merely bounded above $kT ln (\frac{kT}{\epsilon}\cdot G)$, the information content of the circuit may grow sublogarithmically with $G$. All we can say with confidence is that the information content of the circuit is at least $m_0$, and therefore the initialization energy is at least on the order of $m_0\cdot kT$.

Thus far, we have only given asymptotic scalings for the relation between gate time and per-gate energy, assuming a fixed temperature. However, if we make the heuristic assumption that the rate at which gates are traversed due to brownain motion is no more than $\frac{h}{4kT}$, following the Margolus-Levitin theorem, then we can specify a lower bound, independent of temperature, on the per-gate energy $\epsilon$ required to perform $G$ sequential operations in time $t$: 

\[
\epsilon > \frac{hG}{4t}.
\]

Finally, it is worth commenting on the feasibility of Brownian computation for quantum computers. Brownian computation was originally proposed as a way to improve the thermodynamic efficiency of classical computation. It should be noted that many of the techniques that have been proposed for fault tolerance in quantum compuation are thermodynamically irreversible, in particular, syndrome measurement and magic state preparation. These techniques cannot be used in a Brownian mode of computation. However, there are some proposed techniques, such as the use of Fibonacci anyons for universal quantum computation, that may be able to achieve fault tolerance without requiring significant thermodynamic irreversibility (although even in such cases, the cost of fault tolerance is believed to be polylogarithmic in the size of the circuit.) We will therefore optimistically assume that quantum operations can be implemented in a Brownian fashion.

We now proceed to analyze the asymptotic complexity of classical and quantum algorithms for collision and preimage search. We will generally ignore logarithmic factors. As we are engaged in asymptotic analysis, units are strictly speaking irrelevant, but assuming natural units (e.g. $c = \hbar = k = 1$) may be desirable to keep constant factors small. 
 
\section{Collision Search}

The best known classical algorithm for finding collisions in a random function is the parallel collision search algorithm of Van Oorschot and Wiener. If the range of the function is of order $N$, then, given $M$ parallel processes each with memory $O(1)$ the algorithm can find a collision in expected serial depth $O(\frac{\sqrt{N}}{M})$. The communication cost between threads is negligible compared to overall computational costs as long as $M$ is smaller than $\sqrt{N}$ by at least a logarithmic factor.

An improvement over classical collision search has been claimed by Brassard H{\o}yer and Tapp (BHT). Their algorithm is a serial process consisting of $O(N^{\frac{1}{3}})$ operations and requires a memory of size $N^{\frac{1}{3}}$. This can be generalized to arbitrary memory size, $M<O(N^{\frac{1}{3}})$, giving a serial complexity of $O\left(\sqrt{\frac{N}{M}}\right)$. The BHT algorithm may be further generalized to a parallel algorithm involving $p$ parallel processors and a shared memory $M$, where $p<M<O\left((Np)^{\frac{1}{3}}\right)$. in this case, the serial complexity is $O\left(\sqrt{\frac{N}{Mp}}\right)$.

Bernstein has observed that the BHT algorithm, even if parallelized, does not improve upon the Van Oorschot - Wiener algorithm, when measured in terms of memory and serial depth. Since the BHT algorithm also requires $O\left(\sqrt{\frac{N}{M}}\right)$ random access queries to a memory of size $M$, each requiring $O(M)$ gates, it also does not improve upon Van Oorschot Weiner algorithm when evaluated in terms of circuit size and depth (See Beals et al for a more thorough analysis.) However, BHT does represent an improvement over all classical algorithms in terms of query complexity. Furthermore, the Quantum RAM model of Giovanetti et al. gives a theoretical argument that despite their large gate complexity, quantum memory access operations can be performed at logarithmic energy cost. A question therefore remains whether there exists a physically realistic model of computation where BHT is actually cheaper than the classical algorithms for the same problem. However, if there is such a model, it is not the Brownian model of computation, as we proceed to show:

We first analyze the quantum algorithm, calculating the total energy required to perform a collision search, given a maximum time limit $t$ and a maximum memory size $M$. (Here, we assume, following the quantum RAM model, that the energy complexity of the BHT is dominated by oracle queries rather than memory access): The per operation energy $\epsilon$ scales with the serial complexity divided by $t$, i.e.:

\[
\epsilon_{quant} = O\left(\frac{\sqrt{\frac{N}{Mp}}}{t}\right). 
\]
 
The total energy $E$ is then the product of the parallelism, the serial complexity, and the per operation energy, i.e.:

\[
E_{quant} = O\left(p \cdot \sqrt{\frac{N}{Mp}} \cdot \frac{\sqrt{\frac{N}{Mp}}}{t} \right) = O\left(\frac{N}{Mt} \right).
\]  

Now, we analyze the classical algorithm: The per operation energy again scales with the serial complexity, i.e.:

\[
\epsilon_{cl} = O\left(\frac{\sqrt{N}}{Mt}\right). 
\]

The total energy $E$ is again the product of the parallelism (In this case $p = O(M)$), the serial complexity, and the per operation energy, i.e.:

\[
E_{cl} = O\left( M \cdot \frac{\sqrt{N}}{M} \cdot \frac{\sqrt{N}}{Mt} \right) = O\left(\frac{N}{Mt} \right).
\]

Thus, even under optimistic assumptions within the Brownian model of computation, we find that quantum computers provide no advantage in terms of energy, memory, or time, for solving the collision search problem.  

\section{Preimage Search}

Grover's algorithm finds preimages in a function with domain size $N$ in serial complexity $O(\sqrt N)$. Grover's algorithm can be generalized to take advantage of $M$ parallel processes each mith memory $O(1)$, in which case the serial complexity is reduced to $O\left(\sqrt{\frac{N}{M}}\right)$. If we impement Grover's algorithm in a Brownian fashion, we find that

\begin{equation}\label{TGrover}
\epsilon_{quant} = O\left(\frac{\sqrt{\frac{N}{M}}}{t} \right),
\end{equation}

and,

\begin{equation}\label{EGrover}
E_{quant} = O\left(M \cdot \sqrt{\frac{N}{M}} \cdot \frac{\sqrt{\frac{N}{M}}}{t} \right) = O\left(\frac{N}{t}\right).
\end{equation}

A naive Brownian implementation for classical search would divide the key space among $M$ parallel processes, each of which would deterministically step through$\frac{N}{M}$ keys searching for the correct one. Such a deterministic classical algorithm would require,

\[
\epsilon_{det} = O\left(\frac{N}{Mt}\right), 
\]

and,

\[
E_{det} = O\left( M \cdot \frac{N}{M} \cdot \frac{N}{Mt} \right) = O\left(\frac{N^2}{Mt} \right).
\]

This already allows us to compete with Grover's algorithm if we allow ourselves a memory of size $O(N)$. However, we can exploit the structure, or rather the lack of structure, of the search problem to improve upon this figure. In particular, rather than deterministically stepping through the keys, dissipating a driving energy each time, we can simply allow Brownian motion to drive the system on a random walk through the keyspace. We will still require a latching energy to end the computation, once the correct key has been found, and an initialization energy to create the necessary energy barriers to prevent unwanted transitions from occuring.

If the search is implemented by $M$ parallel processes, each of size $O(1)$, then each process must reach $\frac{N}{M}$ keys.  This requires the processes to operate at a temperature:

\begin{equation}\label{Tpreimage}
kT = O\left(\frac{N}{Mt}\right).
\end{equation}

The initialization energy should be of order $MkT$ i.e.:

\[
E_{init} = O\left(M \cdot \frac{N}{Mt}\right) =  O\left(\frac{N}{t}\right).
\]

This is identical to the energy required by a Brownian implementation of Grover's algorithm. All that remains is to show that the latching energy is negligible. Indeed, we find that the energy required to suppress backwards transitions from the final state for a time of order t is $O\left(kT ln(t kT)\right) = O\left(\frac{N}{Mt}ln\left(\frac{N}{M}\right)\right)$. This is negligible as long as $M$ is at least logarithmic in $N$.

Thus, as with collision search, the quantum and classical preimage search algorithms appear to offer the same tradeoffs between time, energy , and memory:

\begin{equation} \label{Epreimage}
E_{cl} = E_{quant} = O \left(\frac{N}{t}\right).
\end{equation}

\section{Preimage Search at constant Power and Temperature / Energy Scale}

In contrast to the collision search case, matching the time/ memory/ energy tradeoffs of Grover's algorithm with a classical search requires a somewhat unrealistic assumption. We assume that  if a computational process can be accomplished at a temperature $T$ in a time $t$, then an isomorphic computation can also be accomplished at a temperature $\alpha T$ in a time $\frac {T}{\alpha}$. This would be true if physics were scale invariant, but the physics of the real world is almost certainly not scale invariant. A more realistic model would therefore restrict the range of temperatures where a given computation is considered feasible. We will therefore repeat the analysis of the previous section assuming a fixed temperature $T$. For added realism, in addition to memory $M$, and time $t$, we will express the resources required for search in terms of power, $P = \frac{E}{t}$, rather than energy, since a fixed power budget is a more common limitation than a fixed energy budget.

From Equation~\ref{Epreimage} we find:

\[
N=O\left(Pt^2\right).
\]

Plugging this into Equation~\ref{Tpreimage} gives us:
\[
M=O\left(\frac{Pt}{T}\right).
\]

We can now calculate time and memory requirements in terms of $T$, $P$, and $N$:

\begin{align}
t_{cl} = O\left(\sqrt{\frac{N}{P}}\right)\\
M_{cl} = O\left(\frac{\sqrt{NP}}{T}\right)
\end{align}

A similar analysis may be done in the quantum case. Here we use Equation~\ref{TGrover} as a lower bound for $T$. If the per gate energy $\epsilon$ exceeds $kT$, we enter the thermodynamic regime of irreversible computing, as opposed to Brownian computing, at which point the time per gate not only fails to further decrease with increasing $\epsilon$, but must in fact increase to prevent the waste heat from heating the computing system to a temperature higher than $T$. Combining this bound with equation~\ref{EGrover} then yields the following time and memory requirements for Grover search at fixed power and temperature:

\begin{align}
t_{quant} = O\left(\sqrt{\frac{N}{P}}\right)\\
M_{quant} = O\left(\frac{P}{T^2}\right)
\end{align}

Thus we find, fixing power and temperature, that our classical search strategy recovers the squareroot time scaling of Grover's algorithm. However, unlike Grover's algorithm, whose space requirement is determined only by the power budget and maximum operating temperature, the classical algorithm also requires memory that scales, like the time, with the squareroot of the size of the search space.

\section{Conclusion}





% ===========================================================================
\bibliographystyle{splncs}
\bibliography{References}
\end{document}